import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static class TreeNode {
        TreeNode leftNode;
        TreeNode rightNode;
        String val;

        public TreeNode(String val) {
            this.val = val;
        }

        public TreeNode () {}

    }

    static TreeNode root;

    public void creatList () {
        TreeNode A = new TreeNode("A");
        TreeNode B = new TreeNode("B");
        TreeNode C = new TreeNode("C");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E");
        TreeNode F = new TreeNode("F");
        TreeNode G = new TreeNode("G");

        A.leftNode = B;
        A.rightNode = C;
        B.leftNode = D;
        B.rightNode = E;
        C.leftNode = F;
        C.rightNode = G;

        root = A;
    }

    public void preOrder (TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }

    public void inOrder (TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.leftNode);
        System.out.print(root.val + " ");
        inOrder(root.rightNode);
    }

    public void postOrder (TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.leftNode);
        postOrder(root.rightNode);
        System.out.print(root.val + " ");
    }

    public static int nodeSize;

    public int size (TreeNode root) {
        if (root == null) {
            return 0;
        }
        nodeSize++;
        size(root.leftNode);
        size(root.rightNode);
        return nodeSize;
    }

    public int getNodeSize (TreeNode root) {
        if (root == null)
            return 0;
        return getNodeSize(root.leftNode) + getNodeSize(root.rightNode) +1;
    }

    public static int leafNodeSize;

    public int getLeafNodeSize1 (TreeNode root) {
        if (root == null)
            return 0;
        if (root.rightNode == null && root.leftNode == null) {
            return 1;
        } else {
            return getLeafNodeSize1(root.leftNode) + getLeafNodeSize1(root.rightNode);
        }
    }

    public void getLeafNodeSize (TreeNode root) {
        //root == null可以节省很多判断 使得null也能完成递归
        if (root == null)
            return;
        if (root.leftNode == null & root.rightNode == null) {
            leafNodeSize++;
            return;
        } else {
            getLeafNodeSize(root.rightNode);
            getLeafNodeSize(root.leftNode);
        }
    }

    public int getKLevelNodeCount (TreeNode root, int k) {
        if (root == null || k <= 0)
            return 0;
        if (k == 1) {
            return 1;
        } else {
            return getKLevelNodeCount(root.leftNode, k - 1) +
                    getKLevelNodeCount(root.rightNode, k - 1);
        }
    }

    public TreeNode find (TreeNode root, String val) {
        if (root == null) {
            return null;
        } else if (root.val == val) {
            return root;
        } else {
            TreeNode tmpNode = null;
            tmpNode = find(root.leftNode, val);
            if (tmpNode != null) {
                return tmpNode;
            } else {
              tmpNode = find(root.rightNode, val);
              if (tmpNode != null) {
                  return tmpNode;
              }
              return null;
            }
        }
    }

    public int getHeight (TreeNode root) {
        if (root == null)
            return 0;
        else {
            int leftHeight = getHeight(root.leftNode);
            int rightHeight = getHeight(root.rightNode);
            return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
        }
    }

    public int maxDepth (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftD = maxDepth(root.leftNode);
        int rightD = maxDepth(root.rightNode);
        if (Math.abs(leftD - rightD) > 1) {
            return -1;
        } else {
            return leftD > rightD ? leftD + 1 : rightD + 1;
        }
    }

    public boolean isBalanced (TreeNode root) {
        if (root == null) {
            return true;
        }
        int lh = maxDepth(root.leftNode);
        int rh = maxDepth(root.rightNode);
        //任意子树出现不平衡：false
        if (lh == -1 || rh == -1) {
            return false;
        }
        //左右子树都需要是平衡二叉树 && 绝对值差值小于等于1
        return Math.abs(lh-rh) <= 1 && isBalanced(root.leftNode) && isBalanced(root.rightNode);
    }

    public static void main7(String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);

    }

    public static void main6(String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);
        System.out.println();
        System.out.println(binaryTree.find(root,"A").val);
    }

    public static void main5 (String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);
        System.out.println();
        int n = binaryTree.getHeight(root.leftNode);
        System.out.println(n);
    }

    public static void main4(String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);
        System.out.println();
        int n = binaryTree.getKLevelNodeCount(root, 1);
        System.out.println(n);
    }

    public static void main3 (String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);
        System.out.println();
        binaryTree.getLeafNodeSize(root);
        System.out.println(leafNodeSize);
        System.out.println();
        int n = binaryTree.getLeafNodeSize1(root);
        System.out.println(n);

    }

    public static void main2(String[] args) {
        BinaryTree binaryTree =  new BinaryTree();
        binaryTree.creatList();
        binaryTree.inOrder(root);
        System.out.println();
        int n = binaryTree.size(root);
        System.out.println(n);
        n = binaryTree.getNodeSize(root);
        System.out.println(n);
    }

    public static void main1(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.creatList();
        binaryTree.preOrder(root);
        System.out.println();
        binaryTree.inOrder(root);
        System.out.println();
        binaryTree.postOrder(root);

    }
}

class Solution {

    static class TreeNode  {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode (int val) {
            this.val = val;
        }

        public TreeNode () {}
    }

    TreeNode root;
    TreeNode subRoot;
    public void creatList() {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);

        root = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        treeNode4.left = treeNode1;
        treeNode4.right = treeNode2;

        subRoot = treeNode4;
        subRoot.left = treeNode1;
        subRoot.right = treeNode2;
    }

    List<Integer> list = new ArrayList<>();

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(q.right, p.right);
    }

    public boolean isSubtree (TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        } else {
            return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        }
    }

    public boolean isSubtree1 (TreeNode root, TreeNode subRoot) {
        //两个都空：直接true
        if (root == null && subRoot == null) {
            return true;
        }
        //只有一个空：肯分不对
        if ((root == null && subRoot != null) || (root != null && subRoot == null)) {
            return false;
        }

        //都不空 值相等：判断是否子树是否相等
        if (root.val == subRoot.val) {
            return isSameTree(root.right,subRoot.right) && isSameTree(root.left, subRoot.left);
        }
        //都不空 值不相等：判断左右子树是不是相等
        else {
            return isSameTree(root.left, subRoot) || isSameTree(root.right, subRoot);
        }
    }

    public static void main1(String[] args) {
        Solution solution = new Solution();
        solution.creatList();
        TreeNode t1 = new TreeNode(1);

        boolean b = solution.isSubtree1(t1, t1);
        System.out.println(b);
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}
